"""
二分查找（折半查找）---> O(log_2 n)
"""


def bin_search(items, key):
    """
    二分查找
    :param items: 待查找的列表（有序）
    :param key: 待查找的元素
    :return: 找到了返回元素的下标，找不到返回-1
    """
    start, end = 0, len(items) - 1
    while start <= end:
        mid = (start + end) // 2
        if key < items[mid]:
            end = mid - 1
        elif key > items[mid]:
            start = mid + 1
        else:
            return mid
    return -1
